#include "StepByStep.h"

#ifndef DFS

#define PRINTLINK

typedef struct _LinkStru {
  int               Index;
  PredKnowledge    *PC;
  struct _LinkStru *next;
} LinkStru;

typedef struct _Link {
  LinkStru *Front;
  LinkStru *Rear;
} Link;

Link GQ, MQ;

void InitLink(Link *Q)
{
  Q->Front = Q->Rear = NULL;
}

void AppendLink(Link *Q, PredKnowledge *PC)
{
  LinkStru *Pt;

  Pt = (LinkStru *) calloc(1, sizeof(LinkStru));

  Pt->PC = PC;
  if (Q->Rear == NULL) Pt->Index = 1;
  else Pt->Index = (Q->Rear->PC->Level != PC->Level ? 1 : Q->Rear->Index+1);

  if (Q->Rear == NULL) Q->Front = Pt;
  else Q->Rear->next = Pt;

  Q->Rear = Pt;
}

#ifdef PRINTLINK
void PrintLink(Link *Q)
{
  PredKnowledge *Pd;
  LinkStru      *Pt;

  for (Pt = Q->Front; Pt != NULL; Pt = Pt->next) {
    Pd = Pt->PC;
    fprintf(Output, "\nI:%4d, L:%d\t%s", Pt->Index, Pd->Level,
                                         (Pd->Type==NOT ? "not ":""));
    PrintTypedArray(PREDNAME(Pd->PredNo), PREDNUMPARA(Pd->PredNo), Pd->Para);
  }

  fprintf(Output, "\n");
}
#endif

PredKnowledge * GetLink(Link *Q)
{
  PredKnowledge *Pc;
  LinkStru      *Pt;

  Pt = Q->Front;
  Pc = Pt->PC;

  Q->Front = Pt->next;  free(Pt);

  if (Q->Front == NULL) Q->Rear = NULL;

  return Pc;
}

void DeletePCsFromLink(Link *Q, ActKnowledge *ActK)
{
  PredKnowledge *PC;
  ActKnowledge  *ActK1;
  LinkStru      *Pt, *Pt1, *Pt2;

  for (PC = ActK->PC; PC != NULL; PC = PC->next)
    for (ActK1 = PC->Act; ActK1 != NULL; ActK1 = ActK1->next)
      DeletePCsFromLink(Q, ActK1);

  Pt1 = Q->Front;
  Pt = Q->Front = NULL;
  while (Pt1 != NULL) {
    Pt2 = Pt1->next;
    PC = Pt1->PC;
    if (PC->PAct == ActK) free(Pt1);
    else {
           if (Pt == NULL) Q->Front = Pt1;
           else Pt->next = Pt1;
           Pt = Pt1;
    }
    Pt1 = Pt2;
  }

  if (Pt != NULL) Pt->next = NULL;
  Q->Rear = Pt;
}

int HandlePCOfActKnowledge(ActKnowledge *ActK)
{
  PredKnowledge *PC;
  Bool           Ok;
  int            Num;

//fprintf(Output, "\nEEE"); PrintActKnowledge(12, ActK, FALSE); fprintf(Output, "\n");
  Num = 0;
  for (PC = ActK->PC; PC != NULL; PC = PC->next) {
    if (Equal(PC->PredNo)) continue;

    PC->Height = ActK->Height;

    Ok = FindOneCurrentFact(PC);
    if (PC->Type == NOT) Ok = !Ok;
    if (Ok) {
       PC->SAT = PC->Fact = TRUE;
       PC->Height = 0;
       continue;
    }

    if (FindOneNoConfirmFact(PC, NULL)) {
       PC->SAT = TRUE;  PC->Fact = FALSE;
       PC->Height = 0;
       continue;
    }

    if (PC->Height==0 || Static(PC->PredNo) || ExistPCLoop(PC))
       return ERROR;

    Num++;
  }

  if (Num == 0) { ActK->Height = 0; return COMPLETED; }

  for (PC = ActK->PC; PC != NULL; PC = PC->next)
    if (!Equal(PC->PredNo) && !PC->SAT) AppendLink(&GQ, PC);

  return UNCOMPLETED;
}

void ExpandHeightForAction(PredKnowledge *Pd)
{
  PredKnowledge *PC;
  ActKnowledge  *ActK, *ActK1;
  Bool           Delete, HasAction;
  int            Height;

  Height = Pd->Height - 1;

  for (ActK = Pd->Act; ActK != NULL; ActK = ActK1) {
    ActK1 = ActK->next;

    if (ActK->Height!=NEW && ActK->Height!=UNFINISHED) continue;

    if (ActK->Height==UNFINISHED && Height == 0) {
       DeletePCsFromLink(&GQ, ActK);
       DeleteActKnowledge(ActK);
       continue;
    }

    Delete = FALSE;
    ActK->Height = Height;
    for (PC = ActK->PC; PC != NULL; PC = PC->next)
      if (PC->Height < 0) {
         PC->Height = Height;
         HasAction = (PC->Act != NULL);
         ExpandHeightForAction(PC);
         Delete = Delete || (HasAction && PC->Act==NULL);
      }

    if (Delete) DeleteActKnowledge(ActK);
  }
}

void GenerateKnowledgeTreeBFS(PredKnowledge *Pd)
{
  PredKnowledge *PC, *PC1, *PC2;
  ActKnowledge  *ActK, *ActK1, *ActK2, *ActK3, *ActK4;
  PKTree        *Pk;
  Bool           Insert;
  int            i, Idx, Num, Height;

  Pd->Act = NULL;   Pd->CPC = NULL;
  Pd->Fact = TRUE;  Pd->CEffect = NULL;
  Height = (Pd->Height==NEW ? NEW : Pd->Height-1);

  Idx = 1;
  ActK1 = NULL;
  Num = PREDNUMPARA(Pd->PredNo);
  Pk = (Pd->Type==ATOM ? PK : nPK) + Pd->PredNo;
  for (Pk = Pk->next; Pk != NULL; Pk = Pk->next) {
    if (!CheckPredKnowledgeTree(Pk, Pd)) continue;

    PC = Pk->Pred;
PrintPKTree(Pk);

    Pd->Character = (Idx==1 ? PC->Character : NONE);

    for (ActK = PC->Act; ActK != NULL; ActK = ActK->next) {
      ActK2 = CopyActKnowledge(ActK, Pd);

      ChangeParaOfActionByPred(ActK2, Pd);
#ifdef CHANGENAME
      ChangeNameParaOfAction(ActK2, Pd);
#endif

      for (PC = ActK2->PC; PC != NULL; PC = PC->next)
        ChangeOnePCByAction(PC, ActK2->Para);
//fprintf(Output, "\n"); PrintActKnowledge(12, ActK2, FALSE); fprintf(Output, "\n");
    if (!HandlePCsOfNewAction(ActK2)) FreeActKnowledge(ActK2);
    else {
           SortPCsOfAction(ActK2);
           InstanceEffectOfAction(ActK2);

           ActK2->Height = Height;
           for (PC = ActK2->PC; PC != NULL; PC = PC->next) PC->Height = Height;

           ActK2->Index = Idx++;
           if (ActK1 != NULL) InsertActKnowledge(ActK1, ActK2);
           else { Pd->Act = ActK2;  Pd->NumAct++; }

           ActK1 = ActK2;
    }
  }
  }
  if (Pd->Act == NULL) return;

//fprintf(Output, "\n11111 Instance"); PrintPredication(12, Pd, FALSE); fprintf(Output, "\n");
  ActK1 = NULL;  ActK = Pd->Act;
  while (ActK != NULL) {
//  if (ActK->Instance) { ActK1 = ActK; ActK = ActK->next; continue; }

    Idx = ActK->ActNo;  // Delete the action if it exists
    Num = ACTNUMPARA(Idx);
    for (ActK2 = ActK->prev; ActK2 != NULL; ActK2 = ActK2->prev)
      if (Idx == ActK2->ActNo &&
          TypedListInTypedList(Num, ActK->Para, ActK2->Para)) break;

    if (ActK2 != NULL) {
       ActK2 = ActK->next;
       DeleteActKnowledge(ActK);
       ActK = ActK2;
       continue;
    }

    //error
    Idx = 1;  Insert = FALSE;
    for (PC = ActK->PC; PC != NULL; PC = PC->next) {
      if (!Equal(PC->PredNo) && PC->NumNonValue > 0) {
         Insert = InstantActionByOnePC(Idx++, PC) || Insert;
         if (Static(PC->PredNo)) break;
      }
    }

    if (PC != NULL) {
       DeleteActKnowledge(ActK);
       if (ActK1 == NULL) ActK = Pd->Act;
       else ActK = ActK1->next;

       continue;
    }

    // Duplicate acttions for each PC when its Nonvalue isn't 0
    Num = 0;
    for (PC = ActK->PC; PC != NULL; PC = PC->next)
      if (PC->NumNonValue > 0 && !Equal(PC->PredNo)) Num++;

    ActK2 = ActK;
    for (i = 1; i < Num; i++) {
      ActK3 = CopyActKnowledge(ActK2, Pd);

      PC = PC1 = ActK3->PC;
      while (PC1->next != NULL) PC1 = PC1->next;

      PC2 = NULL;
      while (PC->NumNonValue == 0) { PC2 = PC; PC = PC->next; }

      if (PC2 == NULL) ActK3->PC = PC->next;
      else PC2->next = PC->next;

      PC1->next = PC;  PC->next = NULL;

      ActK3->prev = ActK2;
      ActK3->next = ActK4 = ActK2->next;
      ActK2->next = ActK3;
      if (ActK4 != NULL) ActK4->prev = ActK3;
      ActK2 = ActK3;
    }
    // End

    if (!Insert) { ActK1 = ActK;  ActK = ActK->next; }
    else if (ActK1 == NULL) ActK = Pd->Act;
         else ActK = ActK1->next;
  }

  ActK = Pd->PAct;
  if (ActK != NULL) CheckAllPCsOfAction(ActK);

//fprintf(Output, "\n22222 Instance"); PrintPredication(12, Pd, FALSE); fprintf(Output, "\n");
  for (ActK = Pd->Act; ActK != NULL; ActK = ActK2) {
    ActK2 = ActK->next;

    if (ActK->Height == NEW) ActK->Height = UNFINISHED;

    ActK1 = ActK->prev;
    if (ActK1 != NULL &&
        (ActK1->Index==ActK->Index || (int)ActK1->Index/10==ActK->Index)) {
       DeleteActKnowledge(ActK);
    }
    else {
           Num = HandlePCOfActKnowledge(ActK);
           if (Num == ERROR) DeleteActKnowledge(ActK);
           else if (Num == COMPLETED) {
                   Pd->Height = ActK->Height + 1;
                   ExpandHeightForAction(Pd);
         }

    }
  }
//fprintf(Output, "\n33333 Instance"); PrintPredication(12, Pd, FALSE); fprintf(Output, "\n");
}

void GetInfoOfPredication(PredKnowledge *Pd);
void GetInfoOfAction(ActKnowledge *ActK)
{
  PredKnowledge *PC;
  int            Acts;

  Acts = 0;
  for (PC = ActK->PC; PC != NULL; PC = PC->next) {
    GetInfoOfPredication(PC);

    Acts += PC->Acts;
  }

  ActK->Acts = Acts;
}

void GetInfoOfPredication(PredKnowledge *Pd)
{
  ActKnowledge *ActK;
  int           Acts;

  Acts = MAX_HEIGHT;
  for (ActK = Pd->Act; ActK != NULL; ActK = ActK->next) {
    GetInfoOfAction(ActK);
    if (Acts > ActK->Acts) Acts = ActK->Acts;
  }

  if (Pd->Act != NULL) Pd->Acts = Acts + 1;
}

void HandleParentAction(PredKnowledge *Pd)
{
  PredKnowledge *PC;
  ActKnowledge  *ActK;
  int            Height;

  ActK = Pd->PAct;

  if (ActK == NULL) return;

  Height = 0;
  for (PC = ActK->PC; PC != NULL; PC = PC->next) {
    if (PC->Height == UNFINISHED) break;
    if (PC->Height > Height) Height = PC->Height;
  }

  if (PC == NULL) {
     ActK->Height = Height;
     PC = ActK->Parent;
     PC->Height = Height + 1;
     ExpandHeightForAction(PC);
     HandleParentAction(PC);
  }
}

void GenerateKnowledgeTreeByBFS(PredKnowledge *Pd)
{
  PredKnowledge *PC;
  Bool           UnFinished;

  Pd->Height = UNFINISHED;

  InitLink(&GQ);
  AppendLink(&GQ, Pd);

  while (GQ.Front != NULL) {
    PC = GetLink(&GQ);

    UnFinished = (PC->Height == UNFINISHED);

    GenerateKnowledgeTreeBFS(PC);

    if (PC->Act == NULL) {
       while (PC->Act == NULL) {
         DeletePCsFromLink(&GQ, PC->PAct);
         DeleteActKnowledge(PC->PAct);
         PC = PC->Parent;
       }
    }
    else if (UnFinished && PC->Height != UNFINISHED)
            HandleParentAction(PC);

#ifdef PRINTLINK
    PrintLink(&GQ);
#endif
  }

  GetInfoOfPredication(Pd);
//fprintf(Output, "\n"); PrintPredication(12, Pd, FALSE); fprintf(Output, "\n");
}

void ModifyKnowledgeTreeBFS(PredKnowledge *PC)
{
  PredKnowledge *PC1, *Parent;
  ActKnowledge  *ActK1, *ActK2, *ActK3;
  Bool           Ok;
  int            HPc;

  Ok = FindAndInstantOneFact(PC);
  if (PC->Type == NOT) Ok = !Ok;
  if (Ok && !PC->Expand) {
     FreeActionsOfPred(PC);
     PC->SAT = PC->Fact = TRUE;
     return;
  }

  Parent = PC->Parent;
  if (Parent!=NULL && FindOneNoConfirmFact(PC, NULL)) {
     FreeActionsOfPred(PC);
     PC->Fact = FALSE;
     PC->SAT = TRUE;
     return;
  }

  HPc = PC->Height;
  if ((0<=HPc && HPc<=2) || (PC->UComplete && PC->Act==NULL)) {
     FreeActionsOfPred(PC);
     PC->SAT = PC->Fact = FALSE;
     GenerateKnowledgeTreeByBFS(PC);
     return;
  }

  ActK1 = PC->Act;
  if (ActK1 == NULL) { PC->SAT = FALSE;  return; }

  for ( ; ActK1 != NULL; ActK1 = ActK2) {
    ActK2 = ActK1->next;

    ActK3 = ActK1->prev;
    if (ActK3==NULL || (int)ActK3->Index/10!=ActK1->Index)
       for (PC1 = ActK1->PC; PC1 != NULL; PC1 = PC1->next)
         if (!Equal(PC1->PredNo)) AppendLink(&MQ, PC1);
  }
}

Bool ModifyKnowledgeTreeByBFS(PredKnowledge *Pd)
{
  PredKnowledge *PC;

  InitLink(&MQ);
  AppendLink(&MQ, Pd);

  while (MQ.Front != NULL) {
    PC = GetLink(&MQ);

    ModifyKnowledgeTreeBFS(PC);
    if (!PC->SAT && PC->Act == NULL) {
       DeletePCsFromLink(&MQ, PC->PAct);
       DeleteActKnowledge(PC->PAct);
    }

#ifdef PRINTLINK
    fprintf(Output, "\n22222 Instance"); PrintPredication(12, PC); fprintf(Output, "\n");
    PrintLink(&MQ);
#endif
  }

  GetInfoOfPredication(Pd);

  return (Pd->SAT || Pd->Act != NULL);
}

#endif
